﻿namespace Leetcode.N1745;
public class Solution
{
    public bool CheckPartitioning(string s)
    {
        var n = s.Length;
        var flgs = new bool?[n, n];
        for (int i = 0; i < n - 2; i++)
        {
            for (int j = i + 1; j < n - 1; j++)
            {
                if (this.Check(s, 0, i, flgs)
                    && this.Check(s, i + 1, j, flgs)
                    && this.Check(s, j + 1, n - 1, flgs))
                {
                    return true;
                }
            }
        }

        return false;
    }


    private bool Check(string s, int from, int to, bool?[,] flgs)
    {
        if (flgs[from, to] == null)
        {
            if (to - from <= 1)
            {
                flgs[from, to] = s[from] == s[to];
            }
            else
            {
                flgs[from, to] = s[from] == s[to] && this.Check(s, from + 1, to - 1, flgs);
            }
        }
        return flgs[from, to].Value;
    }
}